package com.Algorithm;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author yisl
 * @create 2019-06-10 14:37
 */
public class QuickSort {

    
    /** 
    * @Description: 快速排序的原理:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的)，
     * 比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。
     * 一次循环:从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，
     * 如果没有 继续比较下一个，直到找到第一个比基准值小的值才交换。
     * 找到这个值之后，又从前往后开始比 较，如果有比基准值大的，交换位置，
     * 如果没有继续比较下一个，直到找到第一个比基准值大的 值才交换。
     * 直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值 来说，左右两边就是有序的了。
    * @Param: [arr] 
    * @return: void 
    * @Author: yisl
    * @Date: 2019-06-10 
    */
    //public static void quickSort(int[] arr, int low, int high) {
    //
    //    int start = low;
    //    int end = high;
    //
    //    int key = arr[low];
    //    while (start < end){
    //        //第一次从后往前查
    //        while (end > start && arr[end] >= key){
    //            end --;
    //        }
    //        if (arr[end]<=key){
    //            int temp = arr[end];
    //            arr[end] = arr[start];
    //            arr[start] = temp;
    //        }
    //
    //        //第二次从前往查
    //        while (end > start && arr[start] <= key){
    //            start ++;
    //        }
    //        if (arr[start] >= key){
    //            int temp = arr[start];
    //            arr[start] = arr[end];
    //            arr[end] = temp;
    //        }
    //        System.out.println(Arrays.toString(arr));
    //        //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的 值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
    //    }
    //    //递归
    //    if (start > low){
    //        //左边序列。第一个索引位置到关键值索引-1
    //        quickSort(arr,low,start-1);
    //
    //    }
    //
    //    if (end < high){
    //        quickSort(arr, end + 1, high);
    //    }
    //
    //}

    public static void quickSort(int[] arr, int low, int high) {
        if(low>high)return;
        int i = low;
        int j = high;
        int base = arr[low];
        while(i<j){
            while(i<j&&arr[j]>=base){j--;}
            while(i<j&&arr[i]<=base){i++;}
            swap(arr, i, j);
        }
        swap(arr,low,i);

        quickSort(arr, low, j-1);
        quickSort(arr, j+1, high);

    }
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int[] array = {12,20,5,16,15,2,30,45};
        QuickSort.quickSort2(array, 0, array.length -1);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort1(int[] arr, int low, int high) {
        if(low>high)return;
        int i=low;
        int j=high;
        int base=arr[low];
        while(i<j){
            while(i<j&&arr[j]>=base)j--;
            while(i<j&&arr[i]<=base)i++;
            swap(arr, i, j);
        }
        swap(arr, low, i);

        quickSort(arr, low, j-1);
        quickSort(arr, j+1, high);
    }

    public static void quickSort2(int[] arr, int low, int high) {

        if(low>high)return;
        int i=low;
        int j=high;
        int base=arr[low];
        while(i<j){
            while (i<j&&arr[j]>=base)j--;
            while(i<j&&arr[i]<=base)i++;
            swap(arr,i,j);
        }
        swap(arr, low, i);
        quickSort2(arr, low, j-1);
        quickSort2(arr, j+1, high);

    }




}
